题解 P1858 【多人背包】

发表于 | 更新于

$Description$

求$01$背包前$k$优解的价值和

$Solution$

简单的背包问题。我们知道$01$背包的转移条件是$f_{j}=max(f_{j},f_{j-v_{i}}+w_{i})$，也就是说$f_{j}$只会由$f_{j}$与$f_{j-v_{i}}$转移过来，我们考虑多加一维$k$优解，那么显然，$f_{j,k}$优解依然从$f_{j,p}(1\leqslant p\leqslant k)$与$f_{j-v_{i},p}(1\leqslant p\leqslant k)$转移过来。由于$k$很小，我们只需要用$f_{j,p}$与$f_{j-v_{i},p}$暴力判断第$k$优解更新答案即可。值得注意的是，这里的背包必须装满

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define N 60000
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int v[N],f[N][50],w[N],t[N],ans;
signed main(){
    int k=read(),V=read(),n=read();
    for (int i=1;i<=n;++i)v[i]=read(),w[i]=read();
    for (int i=0;i<=n;++i)
        for (int j=0;j<=V;++j)
            f[i][j]=-inf;
    f[0][1]=0;
    for (int i=1;i<=n;++i)
        for (int j=V;j>=v[i];--j){
            int l1=1,l2=1,cnt=0;
            while (cnt<=k){
                if (f[j][l1]>f[j-v[i]][l2]+w[i])
                    t[++cnt]=f[j][l1++];
                else t[++cnt]=f[j-v[i]][l2++]+w[i];
            }
            for (int p=1;p<=k;++p)f[j][p]=t[p];
        }
    for (int i=1;i<=k;++i)ans+=f[V][i];
    cout<<ans<<endl;
}